/*
day177
2020.2.21
*/
#include<vector>
#include<map> 
#include<iostream>
using namespace std;

class Solution1 {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
    	int size=nums.size();
		vector<int> vec;
		vec.push_back(nums[0]);
		vec.push_back(-1*nums[0]);
		for(int i=1;i<size;++i)
		{
			const int &tem=nums[i];
			int cur_size=vec.size();
			for(int j=0;j<cur_size;++j)
			{
				vec.push_back(vec[j]+tem);
				vec[j]-=tem;
			}
		}
		int res=0;
		for(auto &i : vec)
		{
			if(i==S)
			{
				res++;
			}
		}
		return res;
    }
};


class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
		map<int,int> m;
		m[nums[0]]=1;	
		m[-1*nums[0]]=1;
		
		int size=nums.size();
		for(int i=1;i<size;++i)
		{
			map<int,int> cur_m=m;
			for(const auto p : cur_m)
			{
				int tem=p.first;
				m[tem+nums[i]]++;
				m[tem-nums[i]]++;
			}
		}
		return m[S];
    }
};


int main()
{
	vector<int> nums={1, 1, 1, 1, 1} ;
	int S=3;
	Solution s;
	cout<<s.findTargetSumWays(nums,S)<<endl;
	return 0;
}
